package Tree;


import java.util.LinkedList;
import java.util.Queue;

/**
 *  题目 ：向完全二叉树中添加节点
 *  题目详述 ：
 *
 *  完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1个节点）的，并且所有的节点都尽可能地集中在左侧。
 * 设计一个用完全二叉树初始化的数据结构CBTInserter，它支持以下几种操作：
 *
 * CBTInserter(TreeNode root)使用根节点为root的给定树初始化该数据结构；
 * CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
 * CBTInserter.get_root() 将返回树的根节点。
 *
 */
public class CBTInserter {
    /**
     *  核心思想 ：
     *  (1)使用队列，来进行二叉树的广度优先搜索，
     *      同时队列中保存基本上都是缺少左/右子节点的二叉树节点；
     * （2）完全二叉树
     */
    Queue<TreeNode> queue; // 使用队列来进行二叉树的广度优先搜索
    TreeNode root; //用来保存根节点
    public CBTInserter(TreeNode root) {
        this.root = root;
        queue = new LinkedList<>(); // 初始化用来保存完全二叉树节点的队列
        // 初始化时，需要将完全二叉树的根节点需要加入队列中
        queue.offer(root);
        // 即，在初始化中进行完全二叉树的广度优先搜索，
        // 保证队列中队首节点即为===》 第一个左子节点/右子节点有空缺的节点
        while(queue.peek().left != null && queue.peek().right != null){
            // 即，当队首节点的左右节点都不为空时，等价于 其不是第一个左子节点/右子节点有空缺的节点
            TreeNode pollNode = queue.poll();// 需要将其从队列中删除
            // 同时，将此节点下的左右节点加入到队列中
            // 注意 ：即，需要将此节点的左右节点顺序插入
            queue.offer(pollNode.left);
            queue.offer(pollNode.right);
        }
    }

    public int insert(int v) {
        // 即，取出队首节点（即，第一个左子节点/右子节点有空缺的节点）
        // 用于 当所插入的节点为左节点时，不需要将队首节点删除，只需要将队首节点的左子节点指向新插入的节点即可
        TreeNode parentNode = queue.peek();
        // 即，新建TreeNode节点（用来保存所需要插入的节点）
        TreeNode node = new TreeNode(v);

        if(queue.peek().left == null){
            parentNode.left = node;
        }
        else if (queue.peek().right == null){
            parentNode.right = node;
            queue.poll();
            queue.offer(parentNode.left);
            queue.offer(parentNode.right);
        }
        return parentNode.val;
    }

    public TreeNode get_root() {
        // 使用全局定义的root根节点，直接返回即可
        // root，已经在初始化定义中完全二叉树的根节点
        return root;
    }
    // 二叉树的定义

    /**
     * 分析 ：
     * （1）时间复杂度 ：
     *    get_root方法 ：时间复杂度为O（1）；
     *    insert方法 ：时间复杂度 ：O（1）；
     *    CBTInserter（初始化）方法 ：时间复杂度 ：O（n）
     *    由于需要进行二叉树的广度优先搜索，需要对于近乎一半的节点进行遍历
     * （2）空间复杂度 ：
     *    O（n + q） 其中，q为insert方法调用的次数（即，新插入的节点数量为 q）
     *    二叉树中的节点个数为n + q ；同时，队列中的节点个数为 （n + q）/ 2；
     */
}
